//
// Created by xili on 2024/8/24 15:42.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class RangeFreqQuery {
public:
    unordered_map<int, vector<int>> ump;

    RangeFreqQuery(vector<int> &arr) {
        int i = 0;
        for (auto &it: arr) {
            ump[it].push_back(i++);
        }
    }

    int query(int left, int right, int value) {
        auto it = ump.find(value);
        if (it == ump.end()) {
            return 0;
        }
        auto &a = it->second;
        return ranges::upper_bound(a, right) - ranges::lower_bound(a, left);
    }
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */